Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:

Given the below binary tree and sum = 22,

  1.               5
  2.              / \
  3.             4   8
  4.            /   / \
  5.           11  13  4
  6.          /  \    / \
  7.         7    2  5   1

return

  1. [
  2.    [5,4,11,2],
  3.    [5,8,4,5]
  4. ]

Solution:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.   public List<List<Integer>> pathSum(TreeNode root, int sum) {
  12.     List<List<Integer>> res = new ArrayList<>();
  13.     List<Integer> sol = new ArrayList<>();
  15.     helper(root, sum, sol, res);
  17.     return res;
  18.   }
  20.   void helper(TreeNode root, int sum, List<Integer> sol, List<List<Integer>> res) {
  21.     if (root == null)
  22.       return;
  24.     sol.add(root.val);
  26.     if (root.left == null && root.right == null && root.val == sum) {
  27.       res.add(new ArrayList<>(sol));
  28.     } else {
  29.       helper(root.left, sum - root.val, sol, res);
  30.       helper(root.right, sum - root.val, sol, res);
  31.     }
  33.     sol.remove(sol.size() - 1);
  34.   }
  35. }